//
// Created by luolijun on 2022/3/12.
//
#include <iostream>
#include <string>
#include <vector>

#ifndef ASSERT
#define ASSERT(x) assert(x)
#endif

//struct A;
//struct B;
//
//struct A {
//    B* b;
//};
//
//struct B {
//    A* a;
//};
//
//B _b{&_a};
//A _a{&_b};


struct Txpr {
    std::string name;
    std::vector<Txpr*> childs;
};

Txpr* txpr_alloc(const std::string_view& name, std::initializer_list<Txpr*> childs) {
    auto txpr = new Txpr();
    txpr->name = name;
    txpr->childs.insert(txpr->childs.begin(), childs.begin(), childs.end());
    return txpr;
}

void txpr_free(Txpr* txpr) {
    delete txpr;
}

Txpr* txpr_clone(Txpr* txpr) {
    auto result = txpr_alloc(txpr->name, {});
    for (size_t i = 0; i < txpr->childs.size(); i++) {
        result->childs.push_back(txpr_clone(txpr->childs[i]));
    }
    return result;
}

std::string txpr_text(const Txpr* txpr) {
    std::string result = txpr->name;
    if (txpr->childs.size() > 0) {
        result += "<";
        for (size_t i = 0; i < txpr->childs.size(); i++) {
            if (i > 0) {
                result += ",";
            }
            result += txpr_text(txpr->childs[i]);
        }
        result += ">";
    }

    return result;
}


bool txpr_eq(const Txpr* a, const Txpr* b) {
    if (a->name != b->name) {
        return false;
    }

    if (a->childs.size() != a->childs.size()) {
        return false;
    }

    for (size_t i = 0; i < a->childs.size(); i++) {
        if (!txpr_eq(a->childs[i], b->childs[i])) {
            return false;
        }
    }

    return true;
}

Txpr* txpr_int() {
    return txpr_alloc("int", {});
}

Txpr* txpr_real() {
    return txpr_alloc("real", {});
}

Txpr* txpr_complex() {
    return txpr_alloc("complex", {});
}

Txpr* txpr_string() {
    return txpr_alloc("string", {});
}

Txpr* txpr_list(Txpr* child) {
    return txpr_alloc("list", {child});
}

Txpr* txpr_map(Txpr* key, Txpr* value) {
    return txpr_alloc("map", {key, value});
}

Txpr* txpr_assign(Txpr*& source, Txpr* newTxpr) {
    txpr_free(source);
    source = newTxpr;
    return source;
}

int reduce2(Txpr*& source, const Txpr* target) {
    std::cout << "    TRY: " << txpr_text(source) << " -> " << txpr_text(target) << std::endl;

    if (source->name == target->name) {
        if (source->name == "int") {
            return 0;
        }

        if (source->name == "real") {
            return 0;
        }

        if (source->name == "complex") {
            return 0;
        }

        if (source->name == "string") {
            return 0;
        }

        // 对 list<M> vs list<N> 尝试一下子元素
        if (target->name == "list") {
            return reduce2(source->childs[0], target->childs[0]);
            // TODO list<K> vs list<M> 还有一种可能就是 list 拆套
        }

        // 对 map<K,M> vs map<K, N> 尝试一下子元素
        if (target->name == "map") {
            // map 的 key 必须相同
            if (!txpr_eq(source->childs[0], target->childs[0])) {
                return -1;
            }

            return reduce2(source->childs[1], target->childs[1]);
        }
    }

    // 规则1： int <- real <- complex
    if ((source->name == "complex") && (target->name == "real")) {
        source = txpr_assign(source, txpr_real());
        return 0;
    }

    if ((source->name == "complex") && (target->name == "int")) {
        source = txpr_assign(source, txpr_int());
        return 0;
    }

    if ((source->name == "real") && (target->name == "int")) {
        source = txpr_assign(source, txpr_int());
        return 0;
    }

    // 规则2：T <- list<T>
    if (source->name == "list") {
        return reduce2(source->childs[0], target);
    }

    return -1;
}


// 拆词法
static Txpr* txpr_load(const std::string& name, size_t& pos);
static std::string txpr_next(const std::string& name, size_t& pos);
struct TypeExprLoader {
    Txpr* txpr;

    TypeExprLoader(const std::string& name) {
        txpr = new Txpr();
        txpr->name = name;
    }

    ~TypeExprLoader() {
        txpr_free(txpr);
    }

    TypeExprLoader& expect(const std::string& name, size_t& pos, const std::string& s) {
        auto token = txpr_next(name, pos);
        ASSERT(token == s);
        return *this;
    }

    TypeExprLoader& expect(const std::string& name, size_t& pos) {
        auto factor = txpr_load(name, pos);
        ASSERT(factor != nullptr);
        txpr->childs.push_back(factor);
        return *this;
    }

    Txpr* detach() {
        Txpr* result = txpr;
        txpr = nullptr;
        return result;
    }
};

// 处理词法
static std::string txpr_next(const std::string& name, size_t& pos) {
    while (name[pos] == ' ') {
        pos++;
    }

    switch (name[pos]) {
        case '<':
        case '>':
        case ',':
            return std::string(1, name[pos++]);
        default: {
            int start = pos;
            while (std::isalnum(name[++pos])) {
            }
            return name.substr(start, pos - start);
        }
    }
}

// 处理语法
static Txpr* txpr_load(const std::string& name, size_t& pos) {
    auto token = std::move(txpr_next(name, pos));
    if (token == "list") {
        return TypeExprLoader("list")//
            .expect(name, pos, "<")
            .expect(name, pos)
            .expect(name, pos, ">")
            .detach();
    }

    if (token == "map") {
        return TypeExprLoader("map")//
            .expect(name, pos, "<")
            .expect(name, pos)
            .expect(name, pos, ",")
            .expect(name, pos)
            .expect(name, pos, ">")
            .detach();
    }

    if (std::isalnum(token[0])) {
        return TypeExprLoader(token)
            .detach();
    }

    return nullptr;
}


#define SECTION(xxx)

int main(int argc, char* argv[]) {
    //    SECTION("") {
    //        Txpr* source = txpr_list(txpr_complex());
    //        Txpr* target = txpr_list(txpr_int());
    //        std::cout << txpr_string(source) << " -> " << txpr_text(target) << " : " << (reduce2(source, target) ? "FAIL" : "OK") << std::endl;
    //    }
    //    SECTION("") {
    //        Txpr* source = txpr_list(txpr_complex());
    //        Txpr* target = txpr_int();
    //        std::cout << txpr_string(source) << " -> " << txpr_text(target) << " : " << (reduce2(source, target) ? "FAIL" : "OK") << std::endl;
    //    }
    //    SECTION("") {
    //        size_t pos = 0;
    //        Txpr* source = txpr_load("list<complex>", (pos = 0));
    //        Txpr* target = txpr_load("list<int>", (pos = 0));
    //        std::cout << txpr_string(source) << " -> " << txpr_text(target) << " : \n" << (reduce2(source, target) ? "FAIL" : "OK") << std::endl;
    //    }
    SECTION("") {
        size_t pos = 0;
        Txpr* source = txpr_load("list<map<string, list<real>>>", (pos = 0));
        Txpr* target = txpr_load("list<map<string, int>>", (pos = 0));
        std::cout << txpr_text(source) << " -> " << txpr_text(target) << " : \n"
                  << (reduce2(source, target) ? "FAIL" : "OK") << std::endl;
    }
    return 0;
}